package org.gzc.sort;

import java.util.Arrays;

/**
 * @Description: 选择排序
 * 时间复杂度 O(n^2) ,空间复杂度 O(1)
 * @Author: guozongchao
 * @Date: 2020/8/8 0:26
 */
public class SelectSort implements SortStrategy{
    @Override
    public void sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minVal = array[i];  //临时存放最小值的变量，假设当前数组的第i+1个为最小值
            int minIndex=i;     //临时存放最小值所在的下标
            for (int j = i + 1; j < array.length; j++) {
                if (minVal > array[j]) {    //找到比minVal更小的值,将更小的值和对应的下标存放在临时变量中
                    minVal = array[j];
                    minIndex=j;
                }
            }
            //一趟下来，找到了最小值的位置
            if(minIndex!=i){    //优化 ，如果一趟下来都没有发现更小的值，就跳过该步骤
                array[minIndex]=array[i];
                array[i]=minVal;
            }
            //System.out.println("第"+(i+1)+"趟结果："+ Arrays.toString(array));
        }
    }
}
